#include <vector>
#include <iostream>

using namespace std;

class Solution 
{
public:
    int maxSubArray(vector<int>& nums) 
    {
        if(nums.size() == 0)
        {
            return 0;
        }
        int sum = nums[0];
        int maxSum = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            sum = max(nums[i], sum + nums[i]);
            maxSum = max(sum, maxSum);
        }
        return maxSum;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) 
{
    cout << "[";
    for(int i = 0; i < nums.size(); i++) 
    {
        cout << nums[i];
        if(i < nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() 
{
    Solution solution;
    
    // 测试案例1: [-2,1,-3,4,-1,2,1,-5,4]
    cout << "测试案例1:" << endl;
    vector<int> nums1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "输入: nums = ";
    printArray(nums1);
    cout << endl;
    int result1 = solution.maxSubArray(nums1);
    cout << "输出: " << result1 << endl;
    cout << "期望: 6 (子数组 [4,-1,2,1])" << endl << endl;
    
    // 测试案例2: [1]
    cout << "测试案例2:" << endl;
    vector<int> nums2 = {1};
    cout << "输入: nums = ";
    printArray(nums2);
    cout << endl;
    int result2 = solution.maxSubArray(nums2);
    cout << "输出: " << result2 << endl;
    cout << "期望: 1" << endl << endl;
    
    // 测试案例3: [5,4,-1,7,8]
    cout << "测试案例3:" << endl;
    vector<int> nums3 = {5, 4, -1, 7, 8};
    cout << "输入: nums = ";
    printArray(nums3);
    cout << endl;
    int result3 = solution.maxSubArray(nums3);
    cout << "输出: " << result3 << endl;
    cout << "期望: 23 (整个数组)" << endl << endl;
    
    // 测试案例4: 全负数
    cout << "测试案例4 (全负数):" << endl;
    vector<int> nums4 = {-3, -2, -1, -4};
    cout << "输入: nums = ";
    printArray(nums4);
    cout << endl;
    int result4 = solution.maxSubArray(nums4);
    cout << "输出: " << result4 << endl;
    cout << "期望: -1 (最大的单个元素)" << endl << endl;
    
    // 测试案例5: 全正数
    cout << "测试案例5 (全正数):" << endl;
    vector<int> nums5 = {1, 2, 3, 4, 5};
    cout << "输入: nums = ";
    printArray(nums5);
    cout << endl;
    int result5 = solution.maxSubArray(nums5);
    cout << "输出: " << result5 << endl;
    cout << "期望: 15 (整个数组)" << endl << endl;
    
    // 测试案例6: 交替正负
    cout << "测试案例6 (交替正负):" << endl;
    vector<int> nums6 = {-1, 2, -1, 2, -1};
    cout << "输入: nums = ";
    printArray(nums6);
    cout << endl;
    int result6 = solution.maxSubArray(nums6);
    cout << "输出: " << result6 << endl;
    cout << "期望: 2 (单个元素2)" << endl << endl;
    
    // 测试案例7: 中间有最大子数组
    cout << "测试案例7 (中间有最大子数组):" << endl;
    vector<int> nums7 = {-5, 1, 2, 3, -5};
    cout << "输入: nums = ";
    printArray(nums7);
    cout << endl;
    int result7 = solution.maxSubArray(nums7);
    cout << "输出: " << result7 << endl;
    cout << "期望: 6 (子数组 [1,2,3])" << endl << endl;
    
    // 测试案例8: 大数组
    cout << "测试案例8 (大数组):" << endl;
    vector<int> nums8 = {-2, -3, 4, -1, -2, 1, 5, -3};
    cout << "输入: nums = ";
    printArray(nums8);
    cout << endl;
    int result8 = solution.maxSubArray(nums8);
    cout << "输出: " << result8 << endl;
    cout << "期望: 7 (子数组 [4,-1,-2,1,5])" << endl << endl;
    
    // 测试案例9: 零和正数
    cout << "测试案例9 (零和正数):" << endl;
    vector<int> nums9 = {0, 1, 0, 2, 0};
    cout << "输入: nums = ";
    printArray(nums9);
    cout << endl;
    int result9 = solution.maxSubArray(nums9);
    cout << "输出: " << result9 << endl;
    cout << "期望: 3 (整个数组)" << endl << endl;
    
    // 测试案例10: 单个负数
    cout << "测试案例10 (单个负数):" << endl;
    vector<int> nums10 = {-1};
    cout << "输入: nums = ";
    printArray(nums10);
    cout << endl;
    int result10 = solution.maxSubArray(nums10);
    cout << "输出: " << result10 << endl;
    cout << "期望: -1" << endl << endl;
    
    return 0;
}